package com.leetcode;

/**
 * 130. 被围绕的区域
 *
 * @author fy
 * @date 2022/3/28 10:57
 */
public class Solution130 {

    private int m, n;
    private final int[][] d = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private boolean[][] visited;

    public void solve(char[][] board) {
        if (board == null) {
            return;
        }
        this.m = board.length;
        if (this.m <= 0) {
            return;
        }
        this.n = board[0].length;

        this.visited = new boolean[this.m][this.n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                this.visited[i][j] = false;
            }
        }

        // 遍历四条边将连接的 'O' 进行flood fill
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean isEdge = i == 0 || j == 0 || i == this.m - 1 || j == this.n - 1;
                if (isEdge && board[i][j] == 'O' && !this.visited[i][j]) {
                    dfs(board, i, j);
                }
            }
        }

        // 遍历数组将所有没有访问的 'O' 修改为 'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!this.visited[i][j] && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < this.m && y >= 0 && y < this.n;
    }

    /**
     * 从grid[startX][startY]位置开始, 进行Flood Fill
     *
     * @param board
     * @param x
     * @param y
     */
    private void dfs(char[][] board, int x, int y) {
        this.visited[x][y] = true;
        for (int i = 0; i < this.d.length; i++) {
            int newX = x + this.d[i][0];
            int newY = y + this.d[i][1];
            if (this.inArea(newX, newY) && !this.visited[newX][newY] && board[newX][newY] == 'O') {
                dfs(board, newX, newY);
            }
        }
    }
}
